package com.nlp.trie.unigrambigramSeg;

import java.io.DataInputStream;
import java.io.DataOutputStream;
import java.io.IOException;
import java.util.ArrayDeque;
import java.util.Arrays;

public class BigramMap {
	
	public int[] prevIds;
	public int[] freqs;
	public int id;
	
	public BigramMap(int id, int len) {
		this.id = id;
		prevIds = new int[len];
		freqs = new int[len];
	}
	
	public void put(int prevId, int freq) {
		int index = indexOf(prevId);
		if (index == -1) {
			grow();
			for(index = prevIds.length-1; index > 0 && prevIds[index-1] > prevId; index--) {
				prevIds[index] = prevIds[index-1];
				freqs[index] = freqs[index-1];
			}
		}
		prevIds[index] = prevId;
		freqs[index] = freq;
	}
	
	public int get(int prevId) {
		int index = indexOf(prevId);
		if (index != -1) {
			return freqs[index];
		}
		return -1;
	}

	private void grow() {
		int newLength = prevIds.length+1;
		prevIds = Arrays.copyOf(prevIds, newLength);
		freqs = Arrays.copyOf(freqs, newLength);
		
	}

	public int indexOf(int prevId) {
		int low = 0;
		int high = prevIds.length-1;
		while(low <= high) {
			int mid = low+((high-low) >>> 1);
			int midVal = prevIds[mid];
			if (midVal < prevId) {
				low = mid+1;
			}else if (midVal > prevId) {
				high = mid-1;
			}else {
				return mid;//key found
			}
		}
		return -1;

		/*int low = 0;
		int high = prevIds.length - 1;
		while (low <= high) {
			int mid = low + ((high - low) >>> 1);
			int midVal = prevIds[mid];

			if (midVal < prevId)
				low = mid + 1;
			else if (midVal > prevId)
				high = mid - 1;
			else
				return mid; // key found
		}
		return -1;*/
	
	}

	public void add(int i, int key, int val) {
		prevIds[i] = key;
		freqs[i] = val;
	}
	
	public BigramMap(DataInputStream inStream) throws IOException {
		id = inStream.readInt();
		int len = inStream.readInt();
		prevIds = new int[len];
		freqs = new int[len];
		
		for (int i = 0; i < len; i++) {
			prevIds[i] = inStream.readInt();
			freqs[i] = inStream.readInt();
		}
	}
	
	public void save(DataOutputStream outStream) throws IOException {
		outStream.writeInt(id);
		outStream.writeInt(prevIds.length);
		
		for (int i = 0; i < prevIds.length; i++) {
			outStream.writeInt(prevIds[i]);
			outStream.writeInt(freqs[i]);
		}
	}
	
	@Override
	public String toString() {
		StringBuilder sb = new StringBuilder("BigramMap@");
		for (int i = 0; i < prevIds.length; i++) {
			sb.append ("["); //NOI18N
            sb.append (prevIds[i]);
            sb.append (":"); //NOI18N
            sb.append (freqs[i]);
            sb.append ("]"); //NOI18N
		}
		if (prevIds.length == 0) {
			sb.append("empty"); // NOI18N
		}
		return sb.toString();
	}
	
	public int find(int data) {
		int index = 1;
		while(index < prevIds.length) {
			if (data < prevIds[index]) {
				index = index << 1;
			}else if (data == prevIds[index]) {
				return freqs[index];
			}else {
				index = (index << 1)+1;
			}
		}
		return -1;
	}
	
	public void buildArray(int[] keys, int[] values) {
		sortArrays(keys, values);
		int pos = 1;
		this.prevIds = new int[keys.length+1];
		this.freqs = new int[keys.length+1];
		ArrayDeque<Span> queue = new ArrayDeque<Span>();
		queue.add(new Span(0, keys.length));
		while(!queue.isEmpty()) {
			Span current = queue.pop();
			int rootId = BigramMap.getRoot(current.end - current.start)
					+current.start;
			this.prevIds[pos] = keys[rootId];
			this.freqs[pos] = values[rootId];
			pos++;
			if (rootId > current.start) {
				queue.add(new Span(current.start, rootId));
			}
			rootId++;
			if (rootId < current.end) {
				queue.add(new Span(rootId, current.end));
			}
		}
	}

	private static int getRoot(int num) {
		int n = 1;
		while(n <= num) {
			n = n << 1;
		}
		int m = n >> 1;
		int bottom = num-m+1;
		int leftMaxBottom = m >> 1;
		if (bottom > leftMaxBottom) {
			bottom = leftMaxBottom;
		}
		int index = bottom;
		if (m > 1) {
			index += ((m >> 1) - 1);
		}
		return index;
	}

	private void sortArrays(int[] keys, int[] values) {
		int i,j;
		int temp;
		for (i = 0; i < keys.length-1; i++) {
			for (j = 0;  j< keys.length-1-i; j++) {
				if (keys[j] > keys[j+1]) {
					temp = keys[j];
					keys[j] = keys[j+1];
					keys[j+1] = temp;
					
					temp = values[j];
					values[j] = values[j+1];
					values[j+1] = temp;
				}
			}
		}
		
	}
	
	class Span{
		int start;
		int end;
		public Span(int s, int e) {
			start = s;
			end = e;
		}
	}
}
